package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Code19_WordLadderII {

	public static class Qitem {
		String node;
		int parent_pos;
		int step;

		public Qitem(String node, int parent_pos, int step) {
			this.node = node;
			this.parent_pos = parent_pos;
			this.step = step;
		}
	}

	// 计算两个单词之间不相等的字符个数
	public static boolean connect(String word1, String word2) {
		int cnt = 0;
		for (int i = 0; i < word1.length(); i++) {
			if (word1.charAt(i) != word2.charAt(i)) {
				cnt++;
			}
		}
		// 若两个单词之间只有一个字符不同，则返回true
		return cnt == 1;
	}

	// 构建图
	public static void constructGraph(String beginWord, List<String> wordList, Map<String, List<String>> graph) {
		// 因为有可能遍历的时候重复的遍历到beginWord，此时将has_begin_word的值标记为1
		int has_begin_word = 0;
		for (int i = 0; i < wordList.size(); i++) {
			if (wordList.get(i) == beginWord) {
				has_begin_word = 1;
			}

			graph.put(wordList.get(i), new ArrayList<String>());
		}

		if (has_begin_word == 0) {
			graph.put(beginWord, new ArrayList<String>());
		}
		// 如果两个单词相连，则将其存入邻接表数组中
		for (int i = 0; i < wordList.size(); i++) {
			for (int j = i + 1; j < wordList.size(); j++) {
				if (connect(wordList.get(i), wordList.get(j))) {
					graph.get(wordList.get(i)).add(wordList.get(j));
					graph.get(wordList.get(j)).add(wordList.get(i));
				}
			}
			// 如果路径中不存在重复的beginWord的访问且该点与beginWord相连
			if (has_begin_word == 0 && connect(beginWord, wordList.get(i))) {
				graph.get(beginWord).add(wordList.get(i));
			}
		}
	}

	public static void BFS_graph(String beginWord, String endWord, Map<String, List<String>> graph, List<Qitem> Q,
			List<Integer> end_word_pos) {
		Map<String, Integer> visit = new HashMap<String, Integer>();
		// 记录到达endWord的最小步数
		int min_step = 0;
		// 起始单词的前驱节点为 -1
		Q.add(new Qitem(beginWord, -1, 1));
		visit.put(beginWord, 1);
		// 队列头指针front，指向vector表示的队列头
		int front = 0;
		// 说明队列不空，如果front指向了队列的size，说明队列为空
		while (front != Q.size()) {
			String node = Q.get(front).node;
			int step = Q.get(front).step;
			// step > min_step时，代表所有到达终点的路径都搜索完成了
			if (min_step != 0 && step > min_step) {
				break;
			}
			// 搜索结束时，更新最小步数
			if (node == endWord) {
				min_step = step;
				end_word_pos.add(front);
			}
			// 记录当前节点的所有邻接点
			List<String> neighbors = graph.get(node);
			for (int i = 0; i < neighbors.size(); i++) {
				// 若该邻接点未被访问过或者当前邻接点是另一条路径
				// visit[i]==step+1 说明visit[i]上曾经记录过一个结果
				// 而该结果和step+1的值相等，说明这两个路径的长度是一样的
				if (!visit.containsKey(neighbors.get(i)) || visit.get(neighbors.get(i)) == step + 1) {
					// 将该点压入队列中
					Q.add(new Qitem(neighbors.get(i), front, step + 1));
					// 标记到达邻接点 i的最小步数
					visit.put(neighbors.get(i), step + 1);
				}
			}
			// 向后移动指针
			front++;
		}
	}

	public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
		Map<String, List<String>> graph = new HashMap<>();
		constructGraph(beginWord, wordList, graph);
		List<Qitem> Q = new ArrayList<>();
		List<Integer> end_word_pos = new ArrayList<>();

		BFS_graph(beginWord, endWord, graph, Q, end_word_pos);
		List<List<String>> result = new ArrayList<>();
		for (int i = 0; i < end_word_pos.size(); i++) {
			int pos = end_word_pos.get(i);
			List<String> path = new ArrayList<>();
			while (pos != -1) {
				path.add(Q.get(pos).node);
				pos = Q.get(pos).parent_pos;
			}

			result.add(new ArrayList<String>());
			for (int j = path.size() - 1; j >= 0; j--) {
				result.get(i).add(path.get(j));
			}
		}

		return result;
	}

	public static void main(String[] args) {
		String beginWord = "hit";
		String endWord = "cog";
		List<String> wordList = new ArrayList<String>();
//		{"hot","dot","dog","lot","log","cog"};
		wordList.add("hot");
		wordList.add("dot");
		wordList.add("dog");
		wordList.add("lot");
		wordList.add("log");
		wordList.add("cog");

		List<List<String>> count = findLadders(beginWord, endWord, wordList);
		System.out.println(count);
	}
}

//输入:
//beginWord = "hit",
//endWord = "cog",
//wordList = ["hot","dot","dog","lot","log","cog"]
//
//输出:
//[
//["hit","hot","dot","dog","cog"],
//["hit","hot","lot","log","cog"]
//]
